# class Solution(object):
#     def beautySum(self, s):
#         n = len(s)
#         prefix = [[0 for _ in range(26)] for _ in range(n)]
#         ans = 0
#         for index, c in enumerate(s):
#             w = ord(c) - ord('a')
#             if index > 0:
#                 for i in range(26):
#                     prefix[index][i] = prefix[index - 1][i]
#             prefix[index][w] += 1
#             if index >= 2:
#                 for last in range(index - 1):
#                     min_val = float('inf')
#                     max_val = - float('inf')
#                     if last == 0:
#                         for i in range(26):
#                             if prefix[index][i] > 0:
#                                 min_val = min(min_val, prefix[index][i])
#                                 max_val = max(max_val, prefix[index][i])
#                     else:
#                         for i in range(26):
#                             if prefix[index][i] - prefix[last - 1][i] > 0:
#                                 min_val = min(min_val, prefix[index][i] - prefix[last - 1][i])
#                                 max_val = max(max_val, prefix[index][i] - prefix[last - 1][i])
#                     ans += max_val - min_val
#         return ans

class Solution(object):
    def beautySum(self, s):
        n = len(s)
        ans = 0
        for k in range(3, n + 1):
            d = {}
            for t in range(k):
                d[s[t]] = d.get(s[t], 0) + 1
            ans += max(d.values()) - min(d.values())
            for t in range(n - k):
                d[s[t]] -= 1
                if not d[s[t]]:
                    d.pop(s[t])
                d[s[t + k]] = d.get(s[t + k], 0) + 1
                ans += max(d.values()) - min(d.values())
        return ans

data = Solution()
s = "aabcb"
print(data.beautySum(s))
